//
// Description: 611. 有效三角形的个数
// Created by Loading on 2021/8/4.
//

#include <bits/stdc++.h>

using namespace std;

// 排序 + 二分
int triangleNumber(vector<int> &nums) {
    int res = 0;

    /* O(n2logn) */
    sort(nums.begin(), nums.end());
    for (int i = 0; i < nums.size(); ++i) {
        for (int j = i + 1; j < nums.size() - 1; ++j) {
            int l = j, r = (int) nums.size() - 1;
            // 二分查找最右端符合条件位置
            while (l < r) {
                int mid = l + r + 1 >> 1;
                if (nums[i] + nums[j] > nums[mid]) {
                    l = mid;
                } else {
                    r = mid - 1;
                }
            }
            res += l - j;
        }
    }

    return res;
}

// 双指针
int triangleNumber2(vector<int> &nums) {
    int res = 0;

    /* O(n2) */
    sort(nums.begin(), nums.end());
    for (int i = 0; i < nums.size(); ++i) {
        int k = i + 1;
        for (int j = i + 1; j < nums.size() - 1; ++j) {
            /* k 可能会出现小于 j 的情况，k ~ j 已经无效，直接指向 j */
            if (k < j) {
                k = j;
            }
            while (k + 1 < nums.size() && nums[i] + nums[j] > nums[k + 1]) {
                ++k;
            }
            res += k - j;
        }
    }

    return res;
}

int main() {
    vector<int> nums = {2, 2, 3, 4};
    cout << triangleNumber(nums) << endl;
    cout << triangleNumber2(nums) << endl;
}